package cn.itcast.algorithm;

import java.util.Arrays;

/**
 * 快速排序
 * 快速排序是非常经典的排序，也是非常常用的排序，主要是找到一个基准进行比较，分成2部分，基准左边的小于基准，基准右边的大于基准
 * create by zhangtian on 2019/1/22
 */
public class QuickSorted {
    public static void main(String[] args) {
        int[] array = {466,552,45,55000,456,158,111,22,423,0,125,1,2,3,22,65} ;

        quickSorted(array,0,array.length-1);

        Arrays.stream(array).forEach(i->System.out.print(i + " "));
    }

    private static void quickSorted(int[] array, int start, int end) {
        if(start < end) {
            // lookForLocation返回一趟快速排序的结果
            // 也就是确定了边界线（边界线实际上就是你用来比较的靶子）
            // 左边的比右边的都小
            int loc = lookForLocation(array, start, end) ;

            // 类似二分法，递归分治的思想，靶子左边和右边的分别递归排序
            quickSorted(array, start, loc - 1);
            quickSorted(array, loc + 1, end);
        }
    }

    private static int lookForLocation(int[] array, int start, int end) {

        int i = start, j = end ;
        // temp就是靶子，也就是我用来分割的基准
        // 我用的是array中第一个元素来进行左边跟右边的划分
        // 好比：44，33，26，78 44是我的基准
        // 这一趟排序后我要将数组变成26 33 44 78
        int temp = array[start] ;
        while(i < j) {
            // 从数组右边找，直到找到比基准小的整数
            while (array[j] >= temp && i < j){
                j-- ;
            }

            // 找到比基准小的数，就将它复制给array的第一个索引的位置
            // 因为第一个索引的位置我用temp记录下来了
            array[i] = array[j] ;
            // 然后从数组左边找，直到找到比基准大的整数
            while (array[i] <= temp && i < j){
                i ++ ;
            }

            // 大于基准的赋值给j位置的整数，
            // 因为前面我已经记录下array[j]的值：array[i] = array[j];
            array[j] = array[i];
        }

        // 最后讲temp中的值赋值回去，因为前面while循环中有一个重复数据
        array[i] = temp;
        // 返回这趟划分的基准的位置(也就是左边小于或等于temp,右边大于或等于temp)
        return i ;
    }
}
